package TDAMap;
import TDAList.*;
import java.util.Comparator;

/**
 * Implementación de un mapeo utilizando hash abierto.
 * @author Gonzalo Arró
 *
 * @param <K> tipo genérico para las claves de las entradas.
 * @param <V> tipo genérico para los valores de las entradas.
 */
public class OpenHashListMap<K,V> implements Map<K,V> {
	
	// Atributos de instancia
	
	protected PositionList<Entry<K,V>>[] listas;
	protected int size, capacidad;
	
	// Constructor
	
	public OpenHashListMap () {
		size = 0;
		listas = (PositionList<Entry<K,V>>[]) new DoublyLinkedList[capacidad=13];
		for (int i = 0; i < capacidad; i++)
			listas[i] = new DoublyLinkedList<Entry<K,V>>();
	}
	
	// Métodos
	
	public int size () {
		// O(1)
		return size;
	}
	
	public boolean isEmpty () {
		// O(1)
		return size == 0;
	}
	
	public V put (K key, V value) throws InvalidKeyException {
		// O(n/N) = O(1)
		checkKey(key);
		if (size/capacidad>0.5)
			reSize();
		Entrada<K,V> e = buscar(key);
		if (e == null) {
			listas[hashValue(key)].addLast(new Entrada<K,V>(key,value));
			size++;
			return null;
		}
		else {
			V toReturn = e.getValue();
			e.setValue(value);
			return toReturn;
		}
	}
	
	public V get (K k) throws InvalidKeyException {
		// O(1+n/N) = O(1,5) = O(1)
        checkKey(k);
		for (Entry<K,V> e : listas[hashValue(k)]) {
			if (e.getKey()==k)
		       return e.getValue();
		    }
		 return null;
	}
	
	public V remove (K k) throws InvalidKeyException {
		// O(1+n/N) = O(1,5) = O(1)
		checkKey(k);
		for (Position<Entry<K,V>> p : listas[hashValue(k)].positions()) {
			if (p.element().getKey()==k) {
		        size--;
		        try {
		            return listas[hashValue(k)].remove(p).getValue();
		        }
		        catch (InvalidPositionException ex) {}
		    }
		}
	    return null;
	}
	
	public Iterable<K> keys() {
		// O(n)
		PositionList<K> toReturn = new DoublyLinkedList<K>();
		for (int i = 0; i < capacidad; i++) {
			for (Entry<K,V> e : listas[i]) {
				toReturn.addLast(e.getKey());
			}
		}
		return toReturn;
	}
	
	public Iterable<V> values() {
		// O(n)
		PositionList<V> toReturn = new DoublyLinkedList<V>();
		for (int i = 0; i < capacidad; i++) {
			for (Entry<K,V> e : listas[i]) {
				toReturn.addLast(e.getValue());
			}
		}
		return toReturn;
	}
	
	public Iterable<Entry<K,V>> entries() {
		// O(n)
		PositionList<Entry<K,V>> toReturn = new DoublyLinkedList<Entry<K,V>>();
		for (int i = 0; i < capacidad; i++) {
			for (Entry<K,V> e : listas[i]) {
				toReturn.addLast(e);
			}
		}
		return toReturn;
	}
	
	// Métodos auxiliares
	
	protected void checkKey (K k) throws InvalidKeyException {
		// O(1)
		if (k == null) 
			throw new InvalidKeyException ("Clave nula");
	}
	
	protected int hashValue (K k) {
		// O(1)
		int toReturn = (int) (((k.hashCode()*2)+1)%capacidad);
		if (toReturn>0)
	    	return toReturn;
		else
			return -toReturn;
	}

	protected void reSize () {
		// O(n)
		PositionList<Entry<K,V>>[] aux = listas;
		listas = (PositionList<Entry<K,V>>[]) new DoublyLinkedList[capacidad*=2];
		for (int i = 0; i < capacidad; i++) {
			listas[i] = new DoublyLinkedList<Entry<K,V>>();
		}
		for (int j = 0; j < aux.length; j++) {
			for (Entry<K,V> e : aux[j]) {
				listas[hashValue(e.getKey())].addLast(e);
			}
		}
	}
	
	protected Entrada<K,V> buscar (K k) {
		// O(n/N) = O(1)
		for (Entry<K,V> e : listas[hashValue(k)]) {
			if (e.getKey().equals(k))
				return (Entrada<K,V>) e;
		}
		return null;
	}
}
